package com.ly.algorithm.DataStructures.problem;

import java.util.*;

/**
 * @Classname Kruskal
 * @Description TODO
 * @Date 2020/5/4 19:41
 * @Author 冷心影翼
 */
public class Kruskal {

    public static void main(String[] args) {
        char[] data = {'A','B','C','D','E','F','G'};
        Graph2 graph = new Graph2(data);
        graph.insertVerxs(0,1,12);
        graph.insertVerxs(0,5,16);
        graph.insertVerxs(0,6,14);
        graph.insertVerxs(1,2,10);
        graph.insertVerxs(1,5,7);
        graph.insertVerxs(2,3,3);
        graph.insertVerxs(2,4,5);
        graph.insertVerxs(2,5,6);
        graph.insertVerxs(3,4,4);
        graph.insertVerxs(4,5,2);
        graph.insertVerxs(4,6,8);
        graph.insertVerxs(5,6,9);
        graph.showGraph();
        graph.sortEdges();
        System.out.println(graph.edgeData);
        graph.kruskal();
        for (EdgeData e: graph.res) {
            if(e.weight!=0) {
                System.out.println(e);
            }
        }
        for (EdgeData e: graph.res) {
            if(e.weight==0) {
                System.out.println(e);
            }
        }
    }
}



class Graph2{
    private int[][] weight;

    /*
    * 边的个数
    */
    private int edgeNum;

    /*
    *顶点数组
    */
    private char[] vertexs;

    public List<EdgeData> res;

    public List<EdgeData> edgeData = new ArrayList<>();

    private static final int INF = Integer.MAX_VALUE;

    public Graph2(char[] vertexs) {
        this.vertexs = vertexs;
        weight = new int[vertexs.length][vertexs.length];
        for (int[] r: weight) {
            Arrays.fill(r,INF);
        }
    }

    public void insertVerxs(int i, int j, int w) {
        weight[i][j] = w;
        weight[j][i] = w;
        edgeNum++;
        edgeData.add(new EdgeData(vertexs[i],vertexs[j],w));
    }

    public void showGraph() {
        for(int[] r:weight) {
            System.out.println(Arrays.toString(r));
        }
        System.out.println(edgeNum);
    }


    public void sortEdges() {
        edgeData.sort(Comparator.comparingInt( it -> it.weight));
    }



    public void kruskal() {
        res = new ArrayList<>();
        int w = 0;
        for (EdgeData edge:edgeData) {
            char start = edge.start;
            char end = edge.end;
            if(isCircle(start,end)) {
               continue;
            }else {
                insertEdge(edge);
                w += edge.weight;
            }
        }
        System.out.println(w);
     }


    public boolean isCircle(char start,char end) {
        for(EdgeData edgeData:res) {
            if( (edgeData.start == start && edgeData.end == end) || (edgeData.start == end && edgeData.end == start)) {
                return true;
            }
        }
        return false;
    }



    public void insertEdge(EdgeData edgeData) {
        List<EdgeData> list = new ArrayList<>();
        for(EdgeData edge:res) {
            if(edgeData.start == edge.end) {
                list.add(new EdgeData(edge.start,edgeData.end,0));
            }
            if(edgeData.end == edge.start) {
                list.add(new EdgeData(edgeData.start,edge.end,0));
            }
        }
        res.addAll(list);
        res.add(edgeData);
    }
}

class EdgeData {
    char start;
    char end;
    int weight;

    public EdgeData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EdgeData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }


}